package com.gyg.程序员面试金典;
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

import java.util.Stack;

/**
 * 解题思路：
 * 这道题的目的其实就是在原来堆栈的基础上，增加一个返回最小值的方法，其他的方法还和原来的一样
 * 在要求时间复杂度必须为1时，就不能使用其他任何的遍历了
 * 使用双栈处理，一个栈存放所有正常的数据，另一个栈专门存放所有的数据对应时，当前栈中的最小值。
 *
 */

/**
 * 面试题 03.02. 栈的最小值
 */
public class T03_02 {
    /**
     * initialize your data structure here.
     */

    public static void main(String[] args) {
        System.out.println("测试开始：");
//        Stack<Integer> stack = new Stack<Integer>();
//        System.out.println(stack.peek());

    }

//    （1）定义一个存放最小数值的栈
    Stack<Integer> minStack = new Stack<Integer>();
//    （2）定义一个存放原始数据的栈
    Stack<Integer> myStack = new Stack<Integer>();
//    （3）定义一个变量接收最小值
    int minNum = Integer.MAX_VALUE;

    public T03_02() {

    }

    /**
     * 插入元素
     * @param x
     */
    public void push(int x) {
//        （4）将当前最小值和插入的值比较
        minNum = minNum < x ? minNum : x;
//        （5）在原始栈中插入正常数据
        myStack.push(x);
//        （6）在辅助栈中存放最小值
        minStack.push(minNum);
    }

    /**
     * 删除栈顶元素
     */
    public void pop() {
//        （7）删除原始栈的栈顶元素
        myStack.pop();
//        （8）在删除原始栈的栈顶元素后，要删除辅助栈对应的栈顶元素
        minStack.pop();
//        （9）由于当栈为空时，peek是会报错的，所以需要判断栈是否为空
        if (minStack.isEmpty()){
            minNum = Integer.MAX_VALUE;
        }else {
//            （10）辅助栈的栈顶元素就是当前原始栈中所有元素的最小值
            minNum = minStack.peek();
        }
    }

    /**
     * 返回栈顶元素
     * @return
     */
    public int top() {
        return myStack.peek();
    }

    /**
     * 返回栈中的最小值
     * @return
     */
    public int getMin() {
        return minNum;
    }
}
